1. Field of the Invention
This invention relates to digital computers capable of parallel processing, and particularly to assigning memory access priorities to the processors in such computers.
2. Description of the Related Art
In engineering and scientific applications, it is typical to find repetitive accesses to memory at fixed address intervals known as strides. Each new access initiated by a processor is for a memory location separated from the last access by the length of the stride. A stride of one means that the processor accesses every word (whose length may vary) in sequence. A stride of two means that every other word is accessed. When interleaved memory elements (i.e., ones in which memory addresses are assigned on the basis of a low-order portion of the memory address) are accessed by the processors, the stride determines a unique sequence of memory accesses known as the access pattern.
Caches have long been used in digital computers, and have been applied to parallel processing, with one cache assigned to each processor. A cache is a high-speed memory containing copies of selected data from the main memory. Memory accesses from a processor come to the cache, which determines whether it currently has a copy of the accessed memory location. If not, a cache "miss" has occurred, and the cache customarily stops accepting new accesses while it performs a main memory access for the data needed by the processor.
Conventionally each cache serves a single processor, but a cache configured so that it may serve multiple processors is disclosed in copending U.S. patent application Ser. No. 757,859, hereby incorporated by reference.
Where several caches are serving multiple processors, it is desirable to minimize simultaneous accesses by different processors to the same cache. One mechanism for doing so is disclosed in the referenced application. Each processor is assigned a fixed priority level, and the caches are interleaved in such a manner that, for selected memory strides, the processors fall into an access pattern in which no simultaneous access requests occur (known as "lockstep").